We study the problem of learning conjunctive concepts from examples on structural domains like the blocks world. This class of concepts is formally defined, and it is shown that even for samples in which each example (positive or negative) is a two-object scene, it is NP-complete to determine if there is any concept in this class that is consistent with the sample. We demonstrate how this result affects the feasibility of Mitchell's version of space approach and how it shows that it is unlikely that this class of concepts is polynomially learnable from random examples alone in the PAC framework of Valiant. On the other hand, we show that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, we allow the learning algorithm to make subset queries. In establishing this result, we calculate the capacity of the hypothesis space of conjunctive concepts in a structural domain and use a general theorem of Vapnik and Chervonenkis.

We show that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant. Our measure of bias is based on the growth function introduced by Vapnik and Chervonenkis, and on the Vapnik-Chervonenkis dimension. Using these bias measurements we analyze the performance of the classical learning algorithm for conjunctive concepts from the perspective of Valiant's learning framework. We then augment this algorithm with a hypothesis simplification routine that uses a greedy heuristic and show how this improves learning performance on simpler target concepts. Improved learning algorithms are also developed for conjunctive concepts with internal disjunction, k-DNF and k-CNF concepts.

We show that the notion of bias in inductive concept learning can be quantified in a way that directly relates to learning performance, and that this quantitative theory of bias can provide guidance in the design of effective learning algorithms. We apply this idea by measuring some common language biases, including restriction to conjunctive concepts and conjunctive concepts with internal disjunction, and, uided by these measurements, develop learning algorithms P or these classes of concepts that have provably good convergence properties. Introduction The theme of this pa er is that the notion of bias in inductive concept learning Ip U86] [R86/ can be quantified in a way that enables us to rove meaningful convergence properties for learning algorit i ms. We measure bias with a combinatorial parameter defined on classes of concepts known as the Vapnik-Chervonenkis dimension (or simply d ensiorr) [VC71/, [P78j', JBEHW86/. The lower the dlmenslon of the class of concepts considered by the learning algorithm, the stronger the bias.